import java.util.StringTokenizer;
import java.util.Stack;

public class MyDC {
    private final char ADD = '+';
    private final char SUBTRACT = '-';
    private final char MULTIPLY = '*';
    private final char DIVIDE = '/';
    private final char LPARE = '(';
    private final char RPARE = ')';
    private Stack<Rational> stack;
    private Stack<Character> stacktwo;

    public MyDC() {
        stack = new Stack<Rational>();
        stacktwo = new Stack<Character>();
    }

    public Rational evaluate(String expr) {
        int i,a;
        Rational op1=new Rational();
        Rational op2=new Rational();
        Rational result=new Rational();
        result.setNumerator(0);
        char token[]=expr.toCharArray();
        for(i=0;i<token.length;i++){
            if (isOperator(token[i])) {
                op2 = (Rational) stack.pop();
                op1 = (Rational)stack.pop();
                result = evalSingleOp(token[i], op1, op2);
                a = result.getNumerator();
                if(a<0){//当两数计算结果为负时返回该值，通过主方法重新生成题目
                    return result;
                }
                stack.push(result);//将结果压栈
            } else {
                Rational num=new Rational();
                num.setNumerator(token[i]-'0');
                stack.push (num);
            }
        }

        return result;
    }

    private boolean isOperator(char token) {
        return (token=='+' || token=='-' ||
                token=='*' || token=='/');
    }

    private Rational evalSingleOp(char operation, Rational op1, Rational op2) {
        Rational result=new Rational();
        result.setNumerator(0);
        switch (operation) {
            case ADD:
                result = op1.add(op2);
                break;
            case SUBTRACT:
                result = op1.sub(op2);
                break;
            case MULTIPLY:
                result = op1.muti(op2);
                break;
            case DIVIDE:
                result = op1.div(op2);
        }

        return result;
    }
    public String trans(String before){
        int i,j=0;
        char step[] = before.toCharArray();
        char after[] = new char[step.length];
        for(i=0;i<step.length;i++) {
            if (step[i] >= '0' && step[i] <= '9') {
                after[j] = step[i];
                j++;
                if(i==(step.length)-1){
                    while(stacktwo.empty()==false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
            else if(stacktwo.empty()||step[i]=='('||stacktwo.peek()=='('||stacktwo.peek()==')') {
                stacktwo.push(new Character(step[i]));
                if(i==(step.length)-1){
                    while(stacktwo.empty()==false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
            else if(step[i]==')') {
                while (stacktwo.peek() != '(') {
                    after[j] = stacktwo.pop();
                    j++;
                }
                stacktwo.pop();
                if(i==(step.length)-1){
                    while(stacktwo.empty()==false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
            else {
                switch (step[i]) {
                    case ADD:
                    case SUBTRACT:
                    {
                        while(stacktwo.peek()=='*'||stacktwo.peek()=='/'||stacktwo.peek()=='+'||stacktwo.peek()=='-'){
                            after[j]=stacktwo.pop();
                            j++;
                            if(stacktwo.empty()){
                                break;
                            }
                        }
                        stacktwo.push(new Character(step[i]));
                        break;
                    }
                    case MULTIPLY:
                    case DIVIDE:
                    {
                        while(stacktwo.peek()=='*'||stacktwo.peek()=='/'){
                            after[j]=stacktwo.pop();
                            j++;
                            if(stacktwo.empty()){
                                break;
                            }
                        }
                        stacktwo.push(new Character(step[i]));
                        break;
                    }
                }
                if(i==(step.length)-1){
                    while(stacktwo.empty()!=false) {
                        after[j]=stacktwo.pop();
                        j++;
                    }
                }
            }
        }
        String str = new String(after);
        return str;
    }
}
